import heapq

# 定义图的节点类
class Node:
    def __init__(self, value):
        self.value = value
        self.neighbors = []
        self.shortest_distance = float('inf')
        self.previous_node = None

# 定义图类
class Graph:
    def __init__(self):
        self.nodes = []

    def add_node(self, value):
        node = Node(value)
        self.nodes.append(node)

    def add_edge(self, start_node, end_node, weight=1):
        start_node.neighbors.append(end_node)
        end_node.neighbors.append(start_node)
        end_node.shortest_distance = min(end_node.shortest_distance, start_node.shortest_distance + weight)

    def find_shortest_loop(self, start_node, end_node):
        # 初始化堆，将起始节点的距离设为 0，并将其加入堆中
        heap = [(0, start_node)]
        visited = set()
        shortest_loop = None

        while heap:
            current_distance, current_node = heapq.heappop(heap)
            if current_node == end_node:
                # 找到最短路径，构建环路
                loop = [end_node]
                current_node = current_node.previous_node
                while current_node is not None:
                    loop.append(current_node)
                    current_node = current_node.previous_node
                loop.reverse()
                shortest_loop = loop
                break
            if current_node in visited:
                continue
            visited.add(current_node)
            for neighbor in current_node.neighbors:
                if neighbor not in visited:
                    new_distance = current_distance + neighbor.shortest_distance
                    if new_distance < neighbor.shortest_distance:
                        neighbor.previous_node = current_node
                        heapq.heappush(heap, (new_distance, neighbor))

        return shortest_loop

# 创建图
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_node(4)
graph.add_node(5)
graph.add_edge(Node(1), Node(2), weight=2)
graph.add_edge(Node(1), Node(3), weight=3)
graph.add_edge(Node(2), Node(3), weight=1)
graph.add_edge(Node(2), Node(4), weight=4)
graph.add_edge(Node(3), Node(4), weight=2)
graph.add_edge(Node(3), Node(5), weight=5)
graph.add_edge(Node(4), Node(5), weight=3)

# 查找最短环路
start_node = 1
end_node = 5
shortest_loop = graph.find_shortest_loop(start_node, end_node)

if shortest_loop:
    print("最短环路: ", shortest_loop)
else:
    print("无法找到最短环路")